package problem131;

import java.util.ArrayList;
import java.util.List;

//131.分割回文串
//https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    List<List<String>> ret = new ArrayList<>();
    List<String> list = new ArrayList<>();
    int len = 0;
    boolean[][] dp;
    public List<List<String>> partition(String s) {
        int n = s.length();
        dp = new boolean[n+1][n+2];
        dp[0][0] = true;
        for(int i = n; i>0; i--) {
            for(int j = i; j<=n; j++) {
                if(s.charAt(i-1) == s.charAt(j-1)) {
                    if(i == j || i+1 == j) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }
            }
        }
        dfs(s, 0);
        return ret;
    }

    private void dfs(String s, int u) {
        if(u == s.length()) {
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = u; i<s.length(); i++) {
            if(dp[u+1][i+1]) {
                list.add(s.substring(u, i+1));
                dfs(s, i+1);
                list.remove(list.size()-1);
            }
        }
    }
}

/**

dp[i][j]: i~j之间的字符串是否为回文

 */